lib/Mi manual de algoritmos/version_maraton_suramericana_2008/src/geometria/monotonechain.cpp

   1 // Implementation of Monotone Chain Convex Hull algorithm.
   2 #include <algorithm>
   3 #include <vector>
   4 using namespace std;
   5
   6 typedef long long CoordType;
   7
   8 struct Point {
   9         CoordType x, y;
  10
  11         bool operator <(const Point &p) const {
  12                 return x < p.x || (x == p.x && y < p.y);
  13         }
  14 };
  15
  16 // 2D cross product.
  17 // Return a positive value, if OAB makes a counter-clockwise turn,
  18 // negative for clockwise turn, and zero if the points are collinear.
  19 CoordType cross(const Point &O, const Point &A, const Point &B)
  20 {
  21         return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
  22 }
  23
  24 // Returns a list of points on the convex hull in counter-clockwise order.
  25 // Note: the last point in the returned list is the same as the first one.
  26 vector<Point> convexHull(vector<Point> P)
  27 {
  28         int n = P.size(), k = 0;
  29         vector<Point> H(2*n);
  30
  31         // Sort points lexicographically
  32         sort(P.begin(), P.end());
  33
  34         // Build lower hull
  35         for (int i = 0; i < n; i++) {
  36                 while (k >= 2 && cross(H[k-2], H[k-1], P[i]) <= 0) k--;
  37                 H[k++] = P[i];
  38         }
  39
  40         // Build upper hull
  41         for (int i = n-2, t = k+1; i >= 0; i--) {
  42                 while (k >= t && cross(H[k-2], H[k-1], P[i]) <= 0) k--;
  43                 H[k++] = P[i];
  44         }
  45
  46         H.resize(k);
  47         return H;
  48 }